package com.Algorithm.DynamicProgramming.三角形问题;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/04/11/13:28
 * @Description:
 * @Target:
 */

// 1 1 2 3 5 8 13 21 34
public class 斐波那契数列 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//        Integer integer = Integer.valueOf(in.readLine());

        for (int i = 1; i < 10; i++) {
            int[] ints = new int[i+1];
            System.out.print(GetResult(i, ints)+" ");
        }

    }


    // 1,2 是1，其他是前一加前二。
    static int GetResult(int i,int[] ints){
        int temp = 0;
        if (ints[i]!=0){
            return ints[i];
        }

        if (i==1||i==2){
            temp = 1;
        }else {
            temp =  GetResult((i-1),ints)+GetResult((i-2),ints);
        }

        ints[i] = temp;
        return temp;

    }
}
